package com.cfwx.datastructure.sort;


/**
 * 堆排序
 * 
 * 堆排序包括两个步骤：
 * (1)初始堆，堆的定义：堆是一个完全二叉树，根结点的值或者大于左右子树的值或者小于左右子树的值，左右子树也是一个堆。
 * (2)调整堆，当初始小顶堆之后，堆顶元素是最小的元素，取出最小的元素与最后一个元素相交换，再把剩下n-1个元素调整成堆,依次调整直到1为止。
 *  初始堆时，终端节点已经是堆不需要调整，非终端节点调整从n/2向上调整成堆，把第一个元素与最后一个元素交换之后从第1个元素开始调整成新堆，只需要对二叉树根节点的一棵子树进行调整。
 *
 */
public class HeapSort {


	public static void heapsort(int[] num) {
		int n = num.length-1;
		// 初始建堆从n/2开始向根调整
		buildHeap(num,n); //将R[1-n]建成初始堆

		for(int i=n;i>1;i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。
		    num[0] =num[1];//num[0]用来做暂存单元
			num[1]=num[i];
			num[i]=num[0]; //将堆顶和堆中最后一个记录交换
			adjustHeap(num, 1, i - 1); //将R[1..i-1]重新调整为堆，交换后仅有R[1]可能违反堆性质
		} //endfor

	}
	
	//初始化创建堆
	public static void buildHeap(int[] num,int n){
		int i;
		for (i = n / 2; i >= 1; i--) {//只需要调整1——2/n的节点为堆
			adjustHeap(num, i, n);
		}
	}

	
	/**
	 * 调整堆
	 * @param num 待调整序列
	 * @param s 调整堆开始位置
	 * @param t 调整堆结束位置
	 */

	public static void adjustHeap(int[] num, int s, int t) {

		int i = s;
		int x = num[s];//暂存堆顶元素值
		for (int j = 2 * i; j <= t; j = 2 * j) {
			if (j < t && num[j] < num[j + 1])
				j = j + 1;//找出子节点中的较大者
			if (x > num[j])//如果根节点已经大于子节点的较大者，满足堆，就不需要调整。
				break;
			num[i] = num[j];//否则将子节点最大值赋给根节点
			i = j;//将这个较大值子节点当做根节点进行子树调整

		}
		num[i] = x;//将最后被交换的那个子节点元素赋予交换后的值x

	}


	public static void main(String[] args) {
		//数组下标是从0开始，将第一个元素置0不参与排序，使待排序序列从下表1开始
		int num[] = new int[] {0,2221, 5, 40, 32, 2,7,111,9,4};
		heapsort(num);
		for (int x = 0; x < num.length-1; x++) {
			System.out.print(num[x+1] + " ");
		}
	}

}

/**
 * 性能分析:

        时间复杂度:

                  堆是一个完全二叉树,设树高为k=log2n+1,从根到叶的调整,关键码比较的次数为2(k-1)，交换的次数至多为k次。所以比较的次数不超过

       2*(log2(n-1)+log2(n-2)+....+log22)<2nlog2n

                   而比较的次数不超过4n.所以堆排序的时间复杂度为O(nlogn),堆排序的平均性能较接近于最坏性能。

       空间复杂度:

                   需要一个单元的辅助空间用于交换,所以辅助空间为O(1).

      稳定性:

                 堆排序调整过程中存在着交换,所以堆排序是一个不稳定的排序算法。

 */

